백준 3190 뱀

백준 3190 뱀은 도스 뱀 게임을 구현하는 문제이다. n*n의 맵이 있다고 가정하고 0,0의 배열의 위치에서 뱀이 시작했을 때 과연 뱀이 몇초후에 죽는지 출력하는 문제이다.

방향 전환 정보와 사과의 위치 정보가 주어지게 되는데 이 뱀을 잘 구현하기 위해서는 list 자료구조를 이용하면 쉽게 구현이 가능하다. list를 통해서 head와 tail에 모두 넣었다 뺐다 할 수 있으므로 뱀의 움직임을 구현하기 쉽다.

( 한번 움직일 때 head는 다음 방향의 좌표를 push하고 tail은 pop하게 되면 간단하다. )

아래의 코드에서는 기본적인 map을 0, snake를 1, 먹이를 2로 표시하여 head가 Area에 존재하지 않거나 1인 부분에 닿으면 게임이 오버되어 t초를 출력하고, 먹이인 2를 먹게되면 몸길이를 1 증가시키도록 구현하였다. 이는 t초에 대한 while 반복문으로 구현이 가능하다.

#pragma warning(disable:4996)
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<algorithm>
#include<list>
#define INF 999999999999
#define ll long long
using namespace std;

int n;
int k, l;

int map[100][100];

deque<pair<int, int>> snake;
queue<pair<int, int>> cmd;
int direction = 0;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

int headx, heady;
int t = 0;

bool inArea(int x, int y)
{
	if (0 <= x&&x < n && 0 <= y&&y < n)
		return true;
	return false;
}

int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &k);
	snake.push_back(make_pair(0, 0));

	for (int i = 0; i < k; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		map[a - 1][b - 1] = 2;
	}

	scanf("%d", &l);
	for (int i = 0; i < l; i++)
	{
		int t;
		char c;
		scanf("%d %c", &t, &c);

		if (c == 'D')
		{
			cmd.push(make_pair(t, 1));
		}
		else
		{
			cmd.push(make_pair(t, -1));
		}
	}

	while (true)
	{

		t++;
		headx += dx[direction];
		heady += dy[direction];

		if (!inArea(headx, heady) || map[headx][heady] == 1)
		{
			printf("%d\n", t);
			return 0;
		}
		if (map[headx][heady] == 0)
		{
			map[snake.back().first][snake.back().second] = 0;
			snake.pop_back();
		}

		snake.push_front(make_pair(headx, heady));
		map[headx][heady] = 1;

		if (cmd.size()>0 && t == cmd.front().first)
		{
			if (direction + cmd.front().second < 0)
				direction = 3;
			else if (direction + cmd.front().second > 3)
				direction = 0;
			else
				direction += cmd.front().second;
			cmd.pop();
		}
	}
}